package com.chj.gaoji.class14;

import java.util.SortedSet;
import java.util.TreeSet;

// https://blog.csdn.net/weixin_42977872/article/details/84592396
public class Code04_Discretization {
	public static int lower_bound(int[] arr, int target) { // 找到第一个大于等于x的数的位置
		int l = 0;
		int r = arr.length;
		while (l < r) {
			int mid = l + (r - l) / 2;
			if (arr[mid] >= target) {
				r = mid;
			} else {
				l = mid + 1;
			}
		}
		return l == arr.length ? -1 : l;
	}

	public static int[] solve(int[] array) {
		SortedSet<Integer> set = new TreeSet<Integer>();
		// 利用TreeSet可以同时实现排序和去重 可以代替c++中的unique实现
		for (int i = 0; i < array.length; ++i) {
			set.add(array[i]);
		}
		// Integer[] b=(Integer[])set.toArray();
		int[] b = new int[set.size()]; // 将去重排序的数组赋值给b数组
		int ct = 0;
		for (int cur : set) {
			b[ct++] = cur;
		}
		for (int i = 0; i < array.length; ++i) {
			array[i] = lower_bound(b, array[i]) + 1; // 利用lower_bound找到该数值的排位(rank)
			// 排名代表大小 越前越小 越后越大
		}
		// 10000000,2,2,123123213离散化成2,1,1,3
		return array;
	}

	public static void main(String[] args) {
		int[] a = { 10000000, 2, 2, 123123213 };
		solve(a);
//		[2, 1, 1, 3]
		System.out.println(a);
	}
}
